//
//  Exist.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/24.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 12. 矩阵中的路径

import UIKit

/*
 剑指 Offer 12. 矩阵中的路径
 
 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

 [["a","b","c","e"],
 ["s","f","c","s"],
 ["a","d","e","e"]]

 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

  

 示例 1：

 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 输出：true
 示例 2：

 输入：board = [["a","b"],["c","d"]], word = "abcd"
 输出：false
 提示：

 1 <= board.length <= 200
 1 <= board[i].length <= 200
 注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/
 */

class Exist: NSObject {

    var resultArr:[[[Int]]] = []
    var targetLenth = 0
    
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        
        //存放可以作为起点的坐标
        var startPoint:[[Int]] = []
        
        let firstChar = word[word.index(word.startIndex, offsetBy: 0)]
        targetLenth = word.count
        
        for i in 0 ..< board.count{
            for j in 0 ..< board[0].count{
                if board[i][j] == firstChar {
                    startPoint.append([i,j])
                }
            }
        }
        let falgArr = [[Bool]](repeating: [Bool](repeating: false, count: board[0].count), count: board.count)
        
        for start in startPoint {
            self.dfs(start, [], board, falgArr, word, 0)
        }
        
        
        return resultArr.count != 0
    }
    
    
    func dfs(_ enterPoint:[Int], _ tmpArr:[[Int]], _ sourceArr:[[Character]], _ flagArr:[[Bool]], _ word:String, _ depth:Int){
        
        if resultArr.count != 0 {
            return
        }
        
        var arr = tmpArr
        var flagArr = flagArr
        if arr.count == targetLenth{
            resultArr.append(arr)
            return
        }
        if depth > word.count-1{
            return
        }
        
        if enterPoint[0] < 0 || enterPoint[1] < 0 || enterPoint[0] > sourceArr.count-1 || enterPoint[1] > sourceArr[0].count-1{
            return
        }
        
        let ret1 = flagArr[enterPoint[0]][enterPoint[1]]
        if ret1 == true {
            return
        }
        
        if arr.count == 3 {
            print("2222")
        }
        

        let cutChar = word[word.index(word.startIndex, offsetBy: arr.count)]
        if sourceArr[enterPoint[0]][enterPoint[1]] != cutChar {
            return
        }
        
        flagArr[enterPoint[0]][enterPoint[1]] = true
        arr.append(enterPoint)
        
        let nextPointUp = [enterPoint[0] - 1, enterPoint[1]]
        let nextPointLeft = [enterPoint[0], enterPoint[1] - 1]
        let nextPointDown = [enterPoint[0] + 1, enterPoint[1]]
        let nextPointRight = [enterPoint[0], enterPoint[1] + 1]
        
        self.dfs(nextPointUp, arr, sourceArr, flagArr, word, depth+1)
        
        self.dfs(nextPointLeft, arr, sourceArr, flagArr, word, depth+1)
        
        self.dfs(nextPointDown, arr, sourceArr, flagArr, word, depth+1)
        
        self.dfs(nextPointRight, arr, sourceArr, flagArr, word, depth+1)
        
        flagArr[enterPoint[0]][enterPoint[1]] = false
        arr.removeLast()
    }
}
